Definition

Consider FF class of nn-variable functions f:{0,1}nโ†’{0,1}f: \{0,1\}^n \to \{0,1\} . Let ๐–ฎ๐–ฏ๐–ณ๐’ฉ\textsf{OPT}_\mathcal{N} be expected evaluation cost of optimal non-adaptive strategy on function ff under costs cc, probabilities pp. Similarly ๐–ฎ๐–ฏ๐–ณ๐’œ\textsf{OPT}_\mathcal{A} for optimal adaptive strategy on ff. Then, the adaptivity gap of the function class FF is

maxfโˆˆFโกsupc,pโก๐–ฎ๐–ฏ๐–ณ๐’ฉ(f,c,p)๐–ฎ๐–ฏ๐–ณ๐’œ(f,c,p).\begin{aligned} \max _{f \in F} \sup _{c,p} \frac{\textsf{OPT}_\mathcal {N}(f,c,p)}{\textsf{OPT}_\mathcal {A}(f,c,p)}. \end{aligned}

(Intuition: compare optimal non-adaptive with optimal adaptive/any algorithm, the adaptivity gap measures how much benefit can be obtained by an adaptive strategy.)

See also

References

  1. L. Hellerstein, D. Kletenik, N. Liu, and R. T. Witter, โ€œAdaptivity Gaps for the Stochastic Boolean Function Evaluation Problem,โ€ in Approximation and Online Algorithms, vol. 13538, P. Chalermsook and B. Laekhanukit, Eds., in Lecture Notes in Computer Science, vol. 13538. , Cham: Springer International Publishing, 2022, pp. 190โ€“210. doi: 10.1007/978-3-031-18367-6_10.
  2. https://nerva.cs.uni-bonn.de/lib/exe/fetch.php/teaching/ws1819/vl-aau/lecturenotes08.pdf